For the past two decades and longer, due to the rapid development of microelectronic technology, the performance and capacity of computer systems has increased explosively. More computing resources mean that it is possible to develop more complex software to deal with complex problems. Furthermore, more computing resources also mean that it is possible to perform more operations in parallel. Thus, parallel architectures and parallel software development has begun to play a key role in information processing. However, the software (such as software containing a plurality of threads) for dealing with complex problems has become more complex itself.
A process is a program or part of a program running on a computer system, or an associated sequence of steps performed by a certain program. Each process includes one or more threads. A thread is a set of instructions, or a specific section of a program, which can execute independently in the program. Thus a thread is basically a lightweight process, which is responsible for performing tasks in a single program. Usually the operating system is responsible for scheduling and executing a plurality of threads. Each thread can include a plurality of objects that cooperate with one another.
An object-oriented program organizes a plurality of objects that cooperate with one another. In conventional techniques, a program can generally be considered as a sequence of instruction sets. In an object-oriented program, each object can receive messages, process data, and send messages to other objects. In an object-oriented program, memory accesses can be considered as accesses to some fields of objects.
An object-oriented program, especially a multi-thread program for parallel processing, may problems in design due to the software complexity. For example, multi-thread processing is often employed in a process or program, to fully utilize system resources, reduce response time of the program, and improve use experiences. Multi-thread software enables the multiple threads to operate in parallel to perform a plurality of tasks, in order to improve the system efficiency. A thread is implemented when it is needed to perform a plurality of tasks at the same time. However, when a program utilizes multiple threads, it becomes necessary to seriously take threads scheduling into account. If scheduled inappropriately, either the program produce an error, or an absurd result is caused. For example, such software may produce the problem of data race or memory leakage when running. One of the approaches to solve such problems is to conduct memory access tracking and process memory access events to find out and solve problems.
Memory access tracking is usually employed in memory leakage analysis, memory overflow analysis, or data race analysis. When two threads access to the same memory address or overlapped memory addresses simultaneously in which at least one of the accesses includes a write operation, if there is no forced constraint on the access order, a data race will occur. In order to detect a data race, information of each memory access location will be recorded, along with the associated access event.
In prior art, accesses to the memory by a program are tracked by instrumented code. The instrumented code generally comprises extra descriptions and instructions. When the tracked program runs, these extra descriptions and instructions run along with the tracked program. These extra descriptions and instructions will invoke a memory access tracking routine to record memory access events.
The principal problem of memory tracking is the memory overhead, as the memory tracking tool will record all information related to memory accesses. Each memory access event is stored into the memory. Hence, for an actual program, such as an object-oriented application, billions of memory access events will be produced during runtime. To record all of those memory access events will occupy a large amount of processing resources and storage space.
For an object-oriented program, when allocating the memory space, a group of object references are initially set to constitute a root, from which all other objects in the program can be referenced. These root object references are composed of all static field references. The central processing unit (CPU) registers the referenced objects, variables stored on the thread stacks, and internal object references maintained during runtime. The memory space occupied by those objects that cannot be accessed from the root is subject to garbage collection.
Garbage collection (GC), also referred to as memory garbage collection, is a common way of automatic memory management. A garbage collector attempts to collect the memory space used by objects, which may not be used by the objects any more. For example, if the program will not access or process an object any more, the memory space allocated to this object is subject to garbage collection.
As mentioned above, the memory space comprises the memory space occupied by the root objects, the memory space occupied by other objects referenced by the root objects, the memory space occupied by the objects referenced by said other objects, and the memory space not occupied by any of the above objects. Such memory space not occupied by any of the above objects will be collected as garbage. After the garbage collection, most garbage collectors will compact the heap. In other words, the garbage collectors may move living objects to new locations in the heap, and the location of a living object can be changed several times during its lifecycle. For example, a heap comprises a plurality of objects for which memory space has been allocated, wherein the root of the application directly references objects A and E. When the object E is added, if it references an object C, the object C is also referenced and allocated memory space. The garbage collectors will query all accessible objects repeatedly.
A garbage collector moves non-garbage objects in the memory, eliminates redundant gaps in the heap, moves objects in the memory, and invalidates the pointers to the objects.
There are some kinds of common garbage collection technologies. A Mark-Sweep mechanism checks whether an object can be accessed directly or indirectly externally. Inaccessible objects will be identified. It is difficult for a Mark-Sweep garbage collector to deal with fragments. At this point, fragments are usually dealt with using a copy and compact technology.
A collector of a Mark-Sweep-Compact (MSC) mechanism compacts data during each data gathering. Thus, it can prevent fragment generation and maintain the order of allocated objects. A collector of the MSC mechanism can provide better processing capability, and this technology has a higher utilization ratio of memory space. The technology is efficient only under the circumstance of less memory requirement, but with poor extendibility.
There are also Generational collectors, which divide the memory into several regions. This technology manages objects in the memory on an age basis. Two regeneration collectors divide the memory into two regions. One is a region for allocating memory, called a nursery region; the other is a region for storing old objects, called an old generation region. When the memory space in the nursery region is entirely occupied, nursery collection is performed to copy accessible objects in the nursery region to the old generation region. When the memory space in the old generation region is entirely occupied, garbage collection is performed to garbage collect all the objects in the old generation region. The regeneration collection is based on an assumption that the lifecycles of most objects are very short, and only the lifecycles of a small portion of objects are longer. The processing capability of a regeneration collector is better, and the system latency is shorter. The technology for memory garbage collection used in the old generation determines the requirement level of memory space and the characteristics of system latency.